#include<string>
#include<vector>
using namespace std;
class Solution {
public:
    string reorganizeString(string S) {
        vector<int>vec(26, 0);
        for (auto& c : S)
            ++vec[c - 'a'];
        int maxIdx = 0;
        for (int i = 1; i < vec.size(); ++i) {
            if (vec[maxIdx] < vec[i])
                maxIdx = i;
        }
        if (vec[maxIdx] > (S.length()+1) / 2) return "";
        int idx = 0;
        for (int i = 0; i < vec.size(); ++i) {
            int index = (i + maxIdx) % 26;
            while (vec[index] > 0) {
                if (idx > S.length())idx = 1;
                S[idx] = index + 'a';
                --vec[index];
                idx += 2;
            }
        }
        return S;

    }
};